package Mytree;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class MyBinarytree {

    public static class TreeNode {
        public char val;
        private TreeNode left;
        private TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode creatTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
//        TreeNode I = new TreeNode('I');


        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.left = H;
//        H.right = I;
        return A;
    }

    public void preorder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preorder(root.left);
        preorder(root.right);
    }

    List<TreeNode> list = new LinkedList<>();

    public List<TreeNode> preorder2(TreeNode root) {
        if (root == null) {
            return list;
        }
        list.add(root);
//        System.out.print(root.val+" ");
        preorder2(root.left);
        preorder2(root.right);
        return list;
    }

    public List<TreeNode> preorder3(TreeNode root) {
        List<TreeNode> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        ret.add(root);
        List<TreeNode> retleft = preorder3(root.left);
        ret.addAll(retleft);
        List<TreeNode> retright = preorder3(root.right);
        ret.addAll(retright);

        return ret;
    }


    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    public List<TreeNode> inOrder2(TreeNode root) {
        List<TreeNode> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        List<TreeNode> left = inOrder2(root.left);
        ret.addAll(left);
        ret.add(root);
        List<TreeNode> right = inOrder2(root.right);
        ret.addAll(left);
        return ret;
    }

    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public List<TreeNode> postOrder2(TreeNode root) {
        List<TreeNode> ret = new ArrayList<>();

        if (root == null) {
            return ret;
        }
        List<TreeNode> left = postOrder2(root.left);
        ret.addAll(left);

        List<TreeNode> right = postOrder2(root.right);
        ret.addAll(right);

        ret.add(root);
        return ret;
    }

    //前序的方式
    public int size = 0;

    public void getsize(TreeNode root) {
        if (root == null) {
            return;
        }
        size++;
        getsize(root.left);
        getsize(root.right);
    }

    //求树的总结点等于求每个结点的左右子树
    public int getsize2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getsize2(root.left) + getsize2(root.right) + 1;
    }

    //求叶子结点
    public int leafsize = 0;

    public void getleafsize(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafsize++;
        }
        getleafsize(root.left);
        getleafsize(root.left);
    }

    //求叶子结点
    public int getleafsize2(TreeNode root) {
        int count = 0;
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            count++;
        }

        int left = getleafsize2(root.left);
        count = count + left;

        int right = getleafsize2(root.left);
        count = count + right;

        return count;
    }

    //求叶子总结点等于左树的结点加右树的结点
    public int getleafsize3(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        return getleafsize3(root.left) + getleafsize3(root.right);
    }

    //求第k层的结点个数（用分解子问题的方式）
    //root第k层的数量=root.left第k-1层的数量+root.right第k-1层的数量
    //直到k==1；
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        else{
            return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }
    }

    //求树的高度(只是利用了上一个方法)
    public int getheigh2(TreeNode root){
        int count=0;

            int i=1;
            while(i>=1){
                if(getKLevelNodeCount(root,i)!=0){
                    count++;
                    i++;
                }
                else{
                    break;
                }
            }
    return count;
    }

    //求树的高度(树的高度=左树与右树高度的最大值+1)
    public int getheigh(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = getheigh(root.left);
        int right = getheigh(root.right);
        return Math.max(left,right)+1;
    }

//下面为晚上自己再重写一遍，有一些在网上编程题
    public int getSize3(TreeNode root){
        if(root==null){
            return 0;
        }

        return getSize3(root.right)+getSize3(root.left)+1;
    }

    public int getLeafsize2(TreeNode root){
        if(root==null){
            return 0;
        }

        if(root.left==null&&root.right==null){
            return 1;
        }
        int leafsize1 = getLeafsize2(root.left);
        int leafsize2 = getLeafsize2(root.right);
        return leafsize1+leafsize2;
    }

    public int getknode(TreeNode root,int k){
        if(root==null){
            return 0 ;
        }
        if(k==1){
            return 1;
        }
        else{
            return getknode(root.left,k-1)+getknode(root.right,k-1);
        }
    }

}
